import random
import math
import matplotlib.pyplot as plt

def generate_random_board():
    board = [random.randint(0, 7) for _ in range(8)]
    return board
def calculate_attack_pairs(board:list):
    pairs = 0
    for i in range(len(board)):
        for j in range(i + 1, len(board)):
            if board[i] == board[j] or abs(board[i] - board[j]) == j - i:
                pairs += 1
    return pairs

def generate_next_state(board):
    next_board = board.copy()
    i = random.randint(0, 7)
    j = random.randint(0, 7)
    next_board[i] = j
    return next_board

def simulated_annealing():
    max_iterations = 1000
    success_count = 0
    total_steps = 0
    convergence_curve=[]
    for _ in range(max_iterations):
        board = generate_random_board()
        steps = 0

        temperature = 10.0
        cooling_rate = 0.9999
        min_temperature = 0.001

        while calculate_attack_pairs(board) > 0 and temperature > min_temperature:
            next_board = generate_next_state(board)
            current_energy = calculate_attack_pairs(board)
            next_energy = calculate_attack_pairs(next_board)
            if next_energy < current_energy:
                board = next_board
            else:
                probability = math.exp((current_energy - next_energy) / temperature)
                if random.random() < probability:
                    board = next_board
            temperature *= cooling_rate
            steps += 1
        if calculate_attack_pairs(board) == 0:
            success_count += 1
            total_steps += steps
        convergence_curve.append(total_steps/success_count)

    plt.plot(convergence_curve)
    plt.xlabel("Number of Runs")
    plt.ylabel("Average Steps to Optimal Solution")
    plt.title("Convergence Curve")
    plt.show()
    return success_count, total_steps / max_iterations
success_count, avg_steps = simulated_annealing()

print("成功次数：", success_count)
print("平均迭代步数：", avg_steps)